package api.array;

//快速查找
//思路思想：选择一个"基准数",通过一次排序将数组的元素分割成两部分(两个分区)，
// 其中一部分都比基准数小，另外一部分都比基准数大。然后再按照上述思想，
// 分别对这两个分区再进行排序。
public class SortDemo {
    //入口

    public static void main(String[] args) {

        int[]arr={2,32,43,54,12,324,3,5,123,21};

        //调用方法
        printArr(arr);
        System.out.println();
        quickSort(arr,0,arr.length-1);
        printArr(arr);


    }

    //进行快排的方法
    public static void quickSort(int[] arr , int minIndex , int maxIndex) {

        if(minIndex<maxIndex){

            int partition = partition(arr, minIndex, maxIndex);
            //对左边进行操作
            quickSort(arr,minIndex,partition-1);
            //对右边进行操作
            quickSort(arr,partition+1,maxIndex);
        }

    }
    //分区方法

    /**
     * 这个方法的主要作用就是进行分区操作，参数
     * arr：         要分区的数组
     * minIndex      指定分区的范围
     * maxIndex      指定分区的范围
     *
     * @param arr
     * @param minIndex
     * @param maxIndex
     * @return
     */
    public static int partition(int[] arr, int minIndex, int maxIndex) {

        //将第一个值拿出来当基准值，并留下一个坑
        int temp = arr[minIndex];

        while (maxIndex > minIndex) {
            //先从右向左

            while (arr[maxIndex] >= temp && maxIndex > minIndex) {
                maxIndex--;
            }
            //填坑
            if (minIndex < maxIndex) {

                //将max挖出，并填入min留下的坑
                arr[minIndex] = arr[maxIndex];

                minIndex++;
            }

            //从左向右
            while (arr[minIndex] <= temp & maxIndex > minIndex) {

                minIndex++;
            }
            //填坑
            if (minIndex < maxIndex) {

                //将minw出，填入max留下的坑
                arr[maxIndex] = arr[minIndex];

                maxIndex--;
            }

        }
        arr[maxIndex] = temp;

        //返回临界值
        return maxIndex;
    }
    // 遍历数组的方法
    public static void printArr(int[] arr){

        for(int x = 0 ; x < arr.length ; x++) {
            System.out.print(arr[x] + " ");
        }

    }
}
